﻿using System;

namespace MinCut
{
    public class Class1
    {
        char[] chs;
        int minCount = -1;
        public int MinCut(string s)
        {
            chs = s.ToCharArray();
            MaxString(0,chs.Length-1);
            return minCount;
        }

        /// <summary>
        /// 使用递归
        /// 使用2个指针，分别从首位开始遍历，当找到第一个回文串时，设置start=end+1,end=chs.Length重新开始，直到start=chs.Length.
        /// 但这样其实有问题，因为，最长的回文子串又可能是从第n个元素到最后，（如aaabaa，其实只需分割一次，a,aabaa即可），以上解法是按序遍历的，并不符合题意。
        /// 需要借助动态规划来解决。
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        public void MaxString(int start,int end)
        {
            if (start==chs.Length)
            {
                return;
            }

            bool res = Palindrome(start, end);

            if (res)
            {
                minCount++;
                start = end + 1;
                end = chs.Length - 1;
            }
            else
            {
                end = end - 1;
            }
            MaxString(start, end);
        }

        public bool Palindrome(int start,int end)
        {
            while (start<end)
            {
                if (chs[start] == chs[end])
                {
                    start++;
                    end--;
                }
                else
                    return false;
            }

            return true;
        }
    }
}
